package cn.leonis.leetcode;

import java.util.Arrays;

/**
 * @author Tobi
 * @date 2021-06-08 9:40
 * 旋转数组
 * leetcode189
 */
public class RotateArraySolution {

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7};
        int k = 3;
        RotateArraySolution solution = new RotateArraySolution();
        solution.rotate2(nums, k);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }

    /**
     * 该算法的时间复杂度和空间复杂度都很高
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int length = nums.length;

        int[] temp = new int[length];

        for (int i = 0; i < k; i++) {
            int last = nums[length - 1];
            temp[0] = last;
            for (int j = 0; j < length - 1; j++) {
                temp[j + 1] = nums[j];
            }
            System.arraycopy(temp, 0, nums, 0, temp.length);
        }

        // System.arraycopy(temp, 0, nums, 0, temp.length);
    }

    /**
     * 多次反转
     * @param nums
     * @param k
     */
    public void rotate1(int[] nums, int k) {
        int length = nums.length;
        k %= length;
        reverse(nums, 0, length - 1 - k);
        reverse(nums, length - k, length - 1);
        reverse(nums, 0, length - 1);
    }

    /**
     * 反转数组
     * @param nums
     * @param start 开始位置
     * @param end 结束位置
     */
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }

    /**
     * 解法三：使用系统函数
     * @param nums
     * @param k
     */
    public void rotate2(int[] nums, int k) {
        int length = nums.length;
        k %= length;
        int[] rightPart = Arrays.copyOfRange(nums, length - k, length);
        System.arraycopy(nums, 0, nums, k, length - k);
        System.arraycopy(rightPart, 0, nums, 0, k);
    }
}
